/***************************************************************************************
* Copyright (c) 2014-2024 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>
#include <memory/vaddr.h>
enum {
  TK_NOTYPE = 256, 
  TK_EQ,       // 等于 ==
  TK_NUM,      // 十进制数
  TK_HEX,      // 十六进制数
  TK_REG,      // 寄存器名称
  TK_NEQ,      // 不等于 !=
  TK_AND,      // 逻辑与 &&
  TK_POINTER,  // 指针解引用（*作为一元运算符）
  TK_NEG,      // 负号
  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},         // 空格

  // 双字符运算符
  {"==", TK_EQ},             // 等于
  {"!=", TK_NEQ},            // 不等于
  {"&&", TK_AND},            // 逻辑与
  
  // 数字和标识符
  {"0[xX][0-9a-fA-F]+", TK_HEX},  // 十六进制数 (0x开头)
  {"[0-9]+", TK_NUM},             // 十进制数
  {"\\$[a-zA-Z0-9]+", TK_REG},    // 寄存器名 ($开头)
  
  // 单字符运算符
  {"\\+", '+'},              // 加号
  {"-", '-'},                // 减号
  {"\\*", '*'},              // 乘号或解引用(*)
  {"/", '/'},                // 除号
  {"\\(", '('},              // 左括号
  {"\\)", ')'},              // 右括号
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        // Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
        //     i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        if(substr_len >= 32) {
          Log("Token's length beyond 32");
          assert(0);
        }
        switch (rules[i].token_type) {
          case TK_NOTYPE : continue;
          case '+':
          case '-':
          case '*':
          case '/':
          case TK_NUM:
          case TK_AND:
          case TK_EQ:
          case TK_NEQ:
          case TK_HEX:
          case TK_REG:
            tokens[nr_token].type = rules[i].token_type;
            strncpy(tokens[nr_token].str, substr_start, substr_len);
            nr_token ++;
            break;
          default: 
            Log("not support it");
            TODO();
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

bool check_parentheses(int p, int q, bool* is_return) {
  if(tokens[p].type != '(' && tokens[q].type != ')') {
    return false;
  }
  if(tokens[p].type == '(' && tokens[q].type == ')') {
    return true;
  }
  int count_of_left = 0;
  for (int i = p + 1; i < q; i ++) {
    if(tokens[i].type == '(') {
      count_of_left ++;
      continue;
    }
    if(tokens[i].type == ')') {
      count_of_left --;
      continue;
    }
    if(count_of_left < 0) {
      *is_return = true;
      return true;
    }
  }
  return true;
  
}

int find_main_op(int p, int q) {
  int l_position = p;
  int r_position = q;
  int current_priority = 1;
  int op_priority = 0;
  int op_psition = 0;
  while (tokens[l_position].type != '(' && l_position < r_position) l_position ++;
  while (tokens[r_position].type != ')' && r_position > l_position) r_position --;

  for (int i = p; i < q; i ++) {
    if ((i > l_position && i < r_position)) continue;
    bool is_op = true;
    switch (tokens[i].type) {
      case TK_AND:
        current_priority = 4;
        break;
      case TK_EQ:
      case TK_NEQ:
        current_priority = 3;
        break;
      case '+':
      case '-':
        current_priority = 2;
        break;
      case '*':
      case '/':
        current_priority = 1;
        break;
      // case TK_POINTER:
      //   current_priority = 0;
      //   break;
      default:
        is_op = false;
    }

    if(is_op && current_priority > op_priority) {
      op_priority = current_priority;
      op_psition = i;
    }
  }

  return op_psition;
}

word_t eval(int p, int q, bool* is_success) {
  bool is_return = false;
  if (p > q) {
    /* Bad expression */
    Log("Bad expression");
    assert(0);
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
    if(tokens[p].type == TK_NUM) {
      return strtoul(tokens[p].str, NULL, 10);
    }
    else if(tokens[p].type == TK_POINTER) {
      vaddr_t vaddr = strtoul(tokens[p].str, NULL, 16);
      return vaddr_read(vaddr, 4);
    }
    else if(tokens[p].type == TK_REG) {
      word_t val = isa_reg_str2val(tokens[p].str, is_success);
      if(!is_success) {
        Log("fail to get reg val");
        return 0;
      }
      return val;
    }
    else if(tokens[p].type == TK_HEX) {
      return strtoul(tokens[p].str, NULL, 16);
    }
    else {
      Log("bad type");
      assert(0);
    }
  }
  else if (check_parentheses(p, q, &is_return) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    if(is_return) {
      is_success = false;
      return 0;
    }
    return eval(p + 1, q - 1, &is_return);
  }
  else {
    int op_position = find_main_op(p, q);
    word_t val1 = eval(p, op_position - 1, is_success);
    if(!is_success) return 0;
    word_t val2 = eval(op_position + 1, q, is_success);
    if(!is_success) return 0;

    switch (tokens[op_position].type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': 
        if (val2 == 0) {
          Log("divide 0 is not allowed");
          assert(0);
        }
        return val1 / val2;
      case TK_EQ: return val1 == val2;
      case TK_NEQ: return val1 != val2;
      case TK_AND: return val1 && val2;
      default: assert(0);
    }
  }
  // Log("unknown false");
  // assert(0);
  // return 0;
}


word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  //判断是不是乘法
  for(int i = 0; i < nr_token; i ++) {
    if(tokens[i].type == '*')
    {
      if (i == 0 || tokens[i - 1].type == '+' || tokens[i - 1].type == '-' ||\
                                 tokens[i - 1].type == '*' || tokens[i - 1].type == '\\' ||\
                                 tokens[i - 1].type == '(')
                                 {
                                  tokens[i].type = TK_POINTER;
                                  strcpy(tokens[i].str, tokens[i + 1].str);
                                  for(int j = i + 1; j < nr_token; j ++) {
                                    tokens[j].type = tokens[j+1].type;
                                    strcpy(tokens[j].str, tokens[j + 1].str);
                                  }
                                  nr_token --;
                                 } 
    }
    //负数解析
    //   else if(tokens[i - 1].type == '-') {
    //     if (i == 0 || (tokens[i - 1].type != TK_NUM && tokens[i - 1].type != TK_HEX && tokens[i - 1].type != TK_REG && tokens[i - 1].type != TK_POINTER && tokens[i - 1].type != ')')) {
    //       tokens[i].type = TK_NUM;
    //       tokens[i].str
    //     }
    //   }
  }

  word_t val = eval(0, nr_token - 1, success);
  if(!success) {
    success = false;
    return 0;
  }
  return val;
}
